package com.ww.springboot.boot.util;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * 描述：
 *
 * @author wanwei
 * @since 2021-07-26 09:38
 */
@Deprecated
public class SudokuUtil23 {

    public static void solveSudoku(char[][] board) {
        int n = board.length;
        Stack<int[]> stack = new Stack<>();
        int x = 0;
        int y = 0;
        //从左上角起
        while (x < n && y < n) {
            //扫描下一个为0的值
            if (board[x][y] != '.') {
                if (x < n - 1) {
                    x++;
                } else {
                    y++;
                    x = 0;
                }
            } else {
                //如果栈为空 并且num=0 则表示无解
                while (true) {
                    //横线不能重复
                    Set<Character> set = new HashSet<>();
                    for (int i = 0; i < board.length; i++) {
                        if (board[x][i] == 0) {
                            continue;
                        }
                        set.add(board[x][i]);
                    }
                    //竖线不能重复
                    for (int i = 0; i < board.length; i++) {
                        if (board[i][y] == '.') {
                            continue;
                        }
                        set.add(board[i][y]);
                    }

                    //9宫格不能重复
                    int xx = x / 3;
                    int yy = y / 3;

                    for (int i = xx * 3; i < (xx + 1) * 3; i++) {
                        for (int j = yy * 3; j < (yy + 1) * 3; j++) {
                            if (board[i][j] == '.') {
                                continue;
                            }
                            set.add(board[i][j]);
                        }
                    }
                    char ch = board[x][y];
                    if (ch == '.') {
                        ch = '0';
                    }
                    char num = '.';
                    for (int i = ch + 1; i <= 49 + 8; i++) {
                        if (set.add((char) i)) {
                            num = (char) i;
                            break;
                        }
                    }
                    board[x][y] = num;
                    if (board[x][y] == '.') {
                        if(stack.isEmpty()){
                            throw new RuntimeException("无解");
                        }
                        board[x][y] = '.';
                        //回退 从栈中取出上一个坐标
                        int[] ii = stack.pop();
                        x = ii[0];
                        y = ii[1];
                        continue;
                    } else {
                        int[] ii = new int[2];
                        ii[0] = x;
                        ii[1] = y;
                        //进一步
                        stack.push(ii);
                        break;
                    }
                }
            }
        }
    }


    /**
     * 获取有可能的值
     *
     * @param x
     * @param y
     * @param arraysNew
     * @param num       当前值
     * @return
     */
    private static Integer getAbleNum(int x, int y, int[][] arraysNew, int num) {
        //横线不能重复
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arraysNew.length; i++) {
            if (arraysNew[x][i] == 0) {
                continue;
            }
            set.add(arraysNew[x][i]);
        }
        //竖线不能重复
        for (int i = 0; i < arraysNew.length; i++) {
            if (arraysNew[i][y] == 0) {
                continue;
            }
            set.add(arraysNew[i][y]);
        }

        //9宫格不能重复
        int xx = x / 3;
        int yy = y / 3;

        for (int i = xx * 3; i < (xx + 1) * 3; i++) {
            for (int j = yy * 3; j < (yy + 1) * 3; j++) {
                if (arraysNew[i][j] == 0) {
                    continue;
                }
                set.add(arraysNew[i][j]);
            }
        }

        for (int i = num + 1; i <= 9; i++) {
            if (set.add(i)) {
                return i;
            }
        }
        //0 表示没有可用值
        return 0;
    }

    public static String print(char[][] arrays) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arrays.length; i++) {
            for (int j = 0; j < arrays[i].length; j++) {
                sb.append(arrays[i][j]).append(" ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}
